There we go, the weekend puzzles started hitting

Code

As is tradition, the weeekend puzzles are harder. This one's about finding the next and previous numbers for some sequence of numbers.

The main thing I'm happy about is realizing that you can do all without any additional allocations after creating the array containing the series you are working on.

10  13  16  21  30  45 -> 68
   3   3   5   9  15 -> 23
     0   2   4   6 -> 8
       2   2   2 -> 2
         0   0 -> 0

So, in general, the main thing to notice for part one is that the result is the sum of the last elements of each "layer" of differences. The result for this example is 68, which is 2 + 6 + 15 + 45.

We can produce the array [0, 0, 2, 6, 15, 45], corresponding to last values of each layer, as follows:

[10, 13, 16, 21, 30, 45] => calculate differences for the first 5 elements
[3, 3, 5, 9, 15, 45] => calculate differences for the first 4 elements
[0, 2, 4, 6, 15, 45] => calculate differences for the first 3 elements
[2, 2, 2, 6, 15, 45] => calculate differences for the first 2 elements
[0, 0, 2, 6, 15, 45] => first two elements are zeroes, we are done

And then the result is simply the sum of the entire array.

In total, the solution looks like this:

fn predict(series: &mut [i64]) -> Option<i64> {
    for n in (1..series.len()).rev() {
	    // Calculate differences for the first `n` elements
        for i in 0..n {
            series[i] = series[i + 1] - series[i];
        }
        // Check if the first `n` elements are zero; if so, we are done.
        if series[..=n].iter().all(|n| *n == 0) {
            return Some(series[n..].iter().copied().sum());
        }
    }
    None
}

Part two is similar, but reproducing the final result is slightly more involved.

5 <- 10  13  16  21  30  45
  5 <-  3   3   5   9  15
   -2 <-  0   2   4   6
      2 <-  2   2   2
        0 <-  0   0

We are now interested in the first value in each column, so we have to swap around what we overwrite. We used to overwrite the left value in each difference, so that the right one could be retained. Now we wanna overwrite the right value, so that the left one can be retained:

[10, 13, 16, 21, 30, 35] => calculate differences for the last 5 elements
[10, 3, 3, 5, 9, 15] => calculate differences for the last 4 elements
[10, 3, 0, 2, 4, 6] => calculate differences for the last 3 elements
[10, 3, 0, 2, 2, 2] => calculate differences for the last 2 elements
[10, 3, 0, 2, 0, 0] => last two elements are zeroes, we are done

The way we arrive at the result now, is that the predicted value a layer up is the difference between the first value for that layer and the predicted value for the layer one deeper.

So, for example, the third layer has a predicted value of -2. The second layer has a first value of 3. So the predicted value for the second layer is 3 - (-2) = 5. We simply need to work our way backwards through our array like this. The code I wrote is this:

fn extrapolate(series: &mut [i64]) -> Option<i64> {
    for n in (1..series.len()).rev() {
	    // Calculate differences for the last `n` elements
        for i in (series.len() - n..series.len()).rev() {
            series[i] -= series[i - 1];
        }
        // Check if the last `n` elements are zero; if so, we are done.
        if series[series.len() - n..].iter().all(|n| *n == 0) {
            let values = series.iter().take(series.len() - n).rev();
            return Some(values.fold(0, |val, step| step - val));
        }
    }
    None
}

Very similar in structure to the previous part.

For what it's worth, that's equivalent to summing the array with alternating signs, so like 10 - 3 + 0 - 2 + 0 - 0. But it's not really performance critical to implement it like that, and I think iterating the extrapolated value from behind sticks closer to what it's derived from.

I don't think I did a very good job of fully explaining the solution, but today explaining is much more difficult than implementing it, and I wanna go play Path of Exile, lmao.